#include <iostream>
#include <QStack>

template <class Type>
struct BTNode {
    BTNode *left;
    Type data;
    BTNode *right;
    BTNode (Type x)
    {
        data = x;
        left = right = NULL;
    }
};

template <class Type> class PostOrder;
/* 二叉树类 */
template <class Type>
class BinaryTree
{
private:
    BTNode<Type> *root;
    friend class PostOrder<Type>;
public:
    BinaryTree (BTNode<Type> *t)
    {
        root = t;
    }
};

/* 树的迭代器, 二叉树 Post-order 迭代器基类 */
template <class Type>
class TreeIterator
{
protected:
    const BinaryTree <Type> &T;  //BT
    const BTNode<Type> *current;
public:
    TreeIterator (const BinaryTree<Type> &BT)
        : T (BT), current (NULL) {}
    virtual ~TreeIterator() {}
    virtual void First() = 0;
    virtual void operator ++() = 0;
    operator bool()
    {
        return current != NULL;
    }
    const Type operator() () const
    {
        if (current != NULL)
            return current->data;
        return (Type) 0;
    }
};

template <class Type>
struct StkNode {
    // Stack node definition
    const BTNode<Type> *Node;  //Node Address
    int PopTime;	//Counter
    StkNode (const BTNode <Type> *N = NULL) : Node (N), PopTime (0) { }
};

/* Post-order 迭代器 */
template <class Type>
class PostOrder: public TreeIterator<Type>
{
    bool renew;
public:
    PostOrder (const BinaryTree<Type> &BT) : TreeIterator<Type> (BT)
    {
        renew = false;
    }
    ~PostOrder() {}
    void First();
    //Seek to the first node in postorder traversal
    void operator ++();
    //Seek to the successor
protected:
    QStack< StkNode<Type> > st;     //Active record stack
};

template <class Type>
void PostOrder<Type>::First()
{
    this->current = this->T.root;
    st.clear();
    renew = true;
    operator++();
}

template <class Type>
void PostOrder<Type>::operator ++()
{
    if (renew) {
        this->current = this->T.root;
        if (this->current)
                st.push_back(StkNode<Type>(this->current));
        renew = false;
    } else if (this->current == this->T.root) {
        this->current = NULL;
        return;
    }
    StkNode<Type> w;
    while (!st.empty()) {
        w = st.pop();

        if (w.PopTime == 0) {
            w.PopTime += 1;
            st.push(w);
            if (w.Node->right != NULL) {
                st.push_back(StkNode<Type>(w.Node->right));
            }
            if (w.Node->left != NULL) {
                st.push_back(StkNode<Type>(w.Node->left));
            }
        } else {
            this->current = w.Node;
            return;
        }
    }
}

int main()
{
    BTNode<int> *p = new  BTNode<int>(6);
    p->left = new BTNode<int>(4);
    p->right = new BTNode<int>(10);
    p->left->left = new BTNode<int>(2);
    p->right->left = new BTNode<int>(8);
    p->right->right = new BTNode<int>(12);

    BinaryTree<int> T (p);
    PostOrder<int> it (T);

    std::cout << std::endl;
    for (it.First(); it; ++it) {
        std::cout << it() << std::endl;
    }
}
